package com.mlh.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 缪林辉
 * @date 2024/4/8 10:24
 * @DESCRIPTION
 */

// 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
// n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
// 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
public class N皇后 {
    //看代码随心录代码写出的
    //其实N皇后逻辑上并不难
    //主要是处理细节比较麻烦一点
    //isValid()方法判断棋子落位是否合法
    //初始化 char的二维数组
    //Array2List()方法 将二维数组转换成字符串数组 记录到结果中
    List<List<String>>res=new ArrayList<>();
    char[][]chess;
    int chessLen;//棋盘长度

    public List<List<String>> method1(int n) {
        chess = new char[n][n];
        for (char[] c : chess) {
            Arrays.fill(c, '.');
        }
        recursion(0);
        return res;
    }

    //N皇后 回溯法核心思路在这里，其实非常的简单
    public void recursion(int row){
        if(row>=chess.length){
            res.add(Array2List());
            return;
        }
        for (int i = 0; i < chess.length; i++) {
            if(!isValid(row,i)){
                continue;
            }
            chess[row][i]='Q';
            recursion(row+1);
            chess[row][i]='.';
        }
    }

    public boolean isValid(int row,int col){
        //竖向检查
        for (int i = 0; i <row; i++) {
            if( chess[i][col]=='Q'){
                return false;
            }
        }
        //135度检查
        for (int i = row-1,j=col-1; i >=0&&j>=0 ; i--,j--) {
            if( chess[i][j]=='Q'){
                return false;
            }
        }
        //45度检查
        for (int i = row-1,j=col+1; i >=0&&j< chess.length; i--,j++) {
            if(chess[i][j]=='Q'){
                return false;
            }
        }
        return true;
    }

    //记录此时棋盘的结果 用字符串数字的形式
    public List Array2List() {
        List<String> list = new ArrayList<>();
        for (char[] c : chess) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }


    public List<List<String>> practice(int n) {
        chessLen=n;
        chess=new char[chessLen][chessLen];
        // 初始化棋盘
        for (char[]row:chess){
            Arrays.fill(row,'.');
        }
        recursionPractice(0);
        return res;
    }
    public void recursionPractice(int row){
        if(row>=chessLen){
            res.add(Array2ListPractice());
            return;
        }
        for (int i = 0; i < chessLen; i++) {
            if(!isValidPractice(row,i)){
                continue;
            }
            chess[row][i]='Q';
            recursionPractice(row+1);
            chess[row][i]='.';
        }
    }
    // 并不用检查全部棋盘，只需要检测自己上面的棋盘
    public boolean isValidPractice(int row,int col){
        //竖向检测
        for (int i = 0; i < row; i++) {
            if(chess[i][col]=='Q'){
                return false;
            }
        }
        //45度检查
        for (int i = row-1,j=col+1;i>=0&&j<chessLen; i--,j++) {
            if(chess[i][j]=='Q'){
                return false;
            }
        }
        // 135度检查
        for (int i = row-1,j=col-1; i>=0&&j>=0 ; i--,j--) {
            if(chess[i][j]=='Q'){
                return false;
            }
        }
        return true;
    }
    
    public List<String> Array2ListPractice() {
        List<String> list = new ArrayList<>();
        for (char[] c : chess) {
            list.add(String.valueOf(c));
        }
        return list;
    }


    public List<List<String>> practice2(int n) {
        char[][]chess=new char[n][n];
        //使用一维数组填充二维数组！！！！！！！！！！！！！！！
        //使用这个方式赋值二维数组，每一行都是temp的引用，改动一行，其他所有行都会进行相同的变化
        // char[]temp=new char[n];
        // Arrays.fill(temp,'.');
        // Arrays.fill(chess,temp);

        // 初始化棋盘
        for (char[]row:chess){
            Arrays.fill(row,'.');
        }
        recursionPractice2(chess,0);
        return res;
    }

    //row是要下的行，还没下下去
    private void recursionPractice2(char[][]chess,int row) {
        if(row>=chess.length){
            res.add(array2ListPractice2(chess));
            return;
        }
        for (int i = 0; i < chess.length; i++) {
            if(!isValidPractice2(chess,row,i)){
                continue;
            }
            chess[row][i]='Q';
            recursionPractice2(chess,row+1);
            chess[row][i]='.';
        }
    }

    private List<String> array2ListPractice2(char[][]chess) {
        List<String> partRes = new ArrayList<>();
        for (char[] c : chess) {
            partRes.add(new String(c));
        }
        return partRes;
    }

    private boolean isValidPractice2(char[][]chess,int row, int col) {
        for (int i = 0; i < row; i++) {
            if(chess[i][col]=='Q'){
                return false;
            }
        }
        //45度检查
        for (int i = row-1,j=col+1;i>=0&&j<chess.length; i--,j++) {
            if(chess[i][j]=='Q'){
                return false;
            }
        }
        // 135度检查
        for (int i = row-1,j=col-1; i>=0&&j>=0 ; i--,j--) {
            if(chess[i][j]=='Q'){
                return false;
            }
        }
        return true;
    }
}
